# 近づける値
goal = 10000000

# 各都道府県の人口
pref = [
    5381733, 1308265, 1279594, 2333899, 1023119, 1123891, 1914039,
    2916976, 1974255, 1973115, 7266534, 6222666, 13515271, 9126214,
    2304264, 1066328, 1154008, 786740, 834930, 2098804, 2031903,
    3700305, 7483128, 1815865, 1412916, 2610353, 8839469, 5534800,
    1364316, 963579, 573441, 694352, 1921525, 2843990, 1404729,
    755733, 976263, 1385262, 728276, 5101556, 832832, 1377187,
    1786170, 1166338, 1104069, 1648177, 1433566
]

min_total = 0
def search(total, pos):
    global min_total
    if pos >= len(pref):
        return
    if total < goal:
        if abs(goal - (total + pref[pos])) < abs(goal - min_total):
            min_total = total + pref[pos]
        search(total + pref[pos], pos + 1)
        search(total, pos + 1)

search(0, 0)
print(min_total)
